import java.util.*;

public class Practice1 {
    //https://leetcode.cn/problems/vvXgSW/description/
    //合并有序链表的变式题, 采用优先级队列, 或者分治类似归并排序
    public ListNode mergeKLists(ListNode[] lists) {
        //建立堆重写比较器
        PriorityQueue<ListNode> p = new PriorityQueue<>((o1,o2) ->{
            return o1.val - o2.val;
        });
        //将头节点全都加入
        for(int i = 0;i < lists.length;i++){
            if(lists[i] != null){
                p.offer(lists[i]);
            }
        }
        //建立头节点
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        //堆没有元素, 就排完序了
        while(p.size() != 0){
            cur.next = p.poll();
            cur = cur.next;
            if(cur.next != null){
                p.offer(cur.next);
            }
        }
        return ret.next;
    }

}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
